{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Square Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #two-pointers #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #双指针 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: judgeSquareSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #平方数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非负整数&nbsp;<code>c</code>&nbsp;，你要判断是否存在两个整数 <code>a</code> 和 <code>b</code>，使得&nbsp;<code>a<sup>2</sup> + b<sup>2</sup> = c</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>c = 5\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>1 * 1 + 2 * 2 = 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>c = 3\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= c &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-square-numbers](https://leetcode.cn/problems/sum-of-square-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-square-numbers](https://leetcode.cn/problems/sum-of-square-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # 判断是否存在两个数,使得他们的平方和为c\n",
    "        '''\n",
    "        a = int(c**(0.5))        # 所选的两个整数如果存在一定在这其中\n",
    "        i,j=0,a\n",
    "        if c==0:\n",
    "            return True\n",
    "        while i<j:\n",
    "            if i**2+j**2==c:\n",
    "                return True\n",
    "            if i**2+j**2>c:\n",
    "                j=j-1\n",
    "            else:\n",
    "                i=i-1\n",
    "        return False\n",
    "        '''\n",
    "        a=0\n",
    "        while a*a<=c:\n",
    "            temp = c-a*a\n",
    "            if temp**0.5==int(temp**0.5):\n",
    "                return True\n",
    "            a=a+1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        i = 0\n",
    "        j = int(c ** 0.5)\n",
    "        while i <= j:\n",
    "            if i**2 + j**2 == c:\n",
    "                return True\n",
    "            if i**2 + j**2 < c:\n",
    "                i += 1\n",
    "            if i**2 + j**2 > c:\n",
    "                j -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        l = 0\n",
    "        r = int(c**0.5)\n",
    "        \n",
    "        while l<=r:\n",
    "            if l*l+r*r==c:\n",
    "                return True\n",
    "            elif l*l+r*r<c:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        print(l, r)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        for i in range(int(c**0.5+1)):\n",
    "            if (c-i**2)**0.5 == int((c-i**2)**0.5):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        a, b = 0, isqrt(c)\n",
    "        while a <= b:\n",
    "            n = a**2 + b**2\n",
    "            if n == c:\n",
    "                return True\n",
    "            elif n > c:\n",
    "                b -= 1\n",
    "            else:\n",
    "                a += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        a = 0\n",
    "        while a * a <= c:\n",
    "            b = sqrt(c - a * a)\n",
    "            if b == int(b):\n",
    "                return True\n",
    "            a += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # 双指针优化\n",
    "        left, right = 0, int(c**0.5)+1\n",
    "        while left<=right:\n",
    "            if left**2+right**2==c:\n",
    "                return True\n",
    "            elif left**2+right**2 > c:\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        l = 0\n",
    "        r = int(c**0.5)\n",
    "        while l <= r:\n",
    "            if c == l**2 + r**2:\n",
    "                return True\n",
    "            elif c < l**2 + r**2:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        i = 0\n",
    "        j = int(c**0.5)+1 \n",
    "        while i <= j :\n",
    "            if i*i +j*j == c:\n",
    "                return True\n",
    "            elif i*i +j*j < c:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        a, b = 0, int(math.sqrt(c))\n",
    "        while a <= b:\n",
    "            if a ** 2 + b ** 2 == c:\n",
    "                return True\n",
    "            if a ** 2 + b ** 2 < c:\n",
    "                a += 1\n",
    "            if a ** 2 + b ** 2 > c:\n",
    "                b -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # if c == 1:\n",
    "        #     return True\n",
    "        elements = range(1, (int(sqrt(c)))+1)\n",
    "        i = 0\n",
    "        j = len(elements)\n",
    "        while i <= j:\n",
    "            if i*i + j*j < c:\n",
    "                i += 1\n",
    "            elif i*i + j*j > c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 0: return True\n",
    "        for a in range(1, int(math.sqrt(c) + 1)):\n",
    "            b = c - a * a\n",
    "            if int(math.sqrt(b)) ** 2 == b:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 0:\n",
    "            return True\n",
    "        for i in range(1,int(c**0.5)+1):\n",
    "            temp = c-i*i\n",
    "            if int(temp**0.5)**2 == temp:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # if c == 1:\n",
    "        #     return True\n",
    "        elements = range(1, (int(sqrt(c)))+1)\n",
    "        i = 0\n",
    "        j = (int(sqrt(c)))+1\n",
    "        while i <= j:\n",
    "            if i*i + j*j < c:\n",
    "                i += 1\n",
    "            elif i*i + j*j > c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        #寻找最小根\n",
    "        j = int(math.sqrt(c))\n",
    "        #后指针j -- > b 值一定小于此值\n",
    "\n",
    "        #建立前指针i --> a 小值0开始\n",
    "        i = 0\n",
    "\n",
    "        while i <=j:\n",
    "            if i**2 + j**2 > c:\n",
    "                j = j - 1\n",
    "            elif i**2 + j**2 < c:\n",
    "                i = i + 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        #寻找最小根\n",
    "        j = int(math.sqrt(c))\n",
    "        #后指针j -- > b 值一定小于此值\n",
    "\n",
    "        #建立前指针i --> a 小值0开始\n",
    "        i = 0\n",
    "\n",
    "        while i <=j:\n",
    "            if i**2 + j**2 > c:\n",
    "                j = j - 1\n",
    "            elif i**2 + j**2 < c:\n",
    "                i = i + 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # if c == 1:\n",
    "        #     return True\n",
    "        i = 0\n",
    "        j = (int(sqrt(c)))+1\n",
    "        while i <= j:\n",
    "            if i*i + j*j < c:\n",
    "                i += 1\n",
    "            elif i*i + j*j > c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 1:\n",
    "            return True\n",
    "\n",
    "        i = 0\n",
    "        j = (int(sqrt(c)))+1\n",
    "        while i <= j:\n",
    "            if i*i + j*j < c:\n",
    "                i += 1\n",
    "            elif i*i + j*j > c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        sqrt = int(c ** 0.5)\n",
    "        a = 0\n",
    "        b = sqrt\n",
    "        while a <= b:\n",
    "            sum = a**2 + b**2\n",
    "            if sum == c:\n",
    "                return True\n",
    "            elif sum < c:\n",
    "                a += 1\n",
    "            else:\n",
    "                b -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        sqrtC = math.sqrt(c)\n",
    "        squre = 0\n",
    "        left, right = 0, int(sqrtC)\n",
    "\n",
    "        while left <= right:\n",
    "            squre = left ** 2 + right ** 2\n",
    "            if squre == c:\n",
    "                return True\n",
    "            elif squre < c:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        left= 0\n",
    "        right = int(c**0.5)+1\n",
    "        while left <=right:\n",
    "            sum =left*left + right*right\n",
    "            if sum == c:\n",
    "                return True\n",
    "            elif sum >c:\n",
    "                right =right -1\n",
    "            else:\n",
    "                left = left +1 \n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        left = 0\n",
    "        right = math.floor(math.sqrt(c))\n",
    "        while left <= right:\n",
    "            print(left, right)\n",
    "            s = left * left + right * right\n",
    "            if s == c:\n",
    "                return True\n",
    "            elif s > c:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return False\n",
    "\n",
    "'''\n",
    "存在两个数的平方和是c\n",
    "\n",
    "如果存在，返回True\n",
    "\n",
    "否则返回False\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        return self.if_sum_of_sqr(c)\n",
    "\n",
    "    def if_sum_of_sqr(self, num):\n",
    "        if num == 0 or num == 1:\n",
    "            return True\n",
    "        maxx = int(num**(1/2))\n",
    "        lst = list(range(maxx+1))\n",
    "        small = 0\n",
    "        big = len(lst)-1\n",
    "        while small <= big:\n",
    "            if lst[small]**2 + lst[big]**2 == num:\n",
    "                return True\n",
    "            elif lst[small]**2 + lst[big]**2 < num:\n",
    "                small += 1\n",
    "            else:\n",
    "                big -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "\n",
    "        res_list = []\n",
    "        t = int(sqrt(c))\n",
    "        for i in range(t+1):\n",
    "            res_list.append(i * i)\n",
    "\n",
    "        for i, n in enumerate(res_list):\n",
    "            if sqrt(c - n) % 1 == 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "SQRS = []\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c):\n",
    "        global SQRS\n",
    "        if len(SQRS) == 0:\n",
    "            for i in range(46341):\n",
    "                SQRS.append(i**2)\n",
    "\n",
    "        res = False\n",
    "        l = len(SQRS)\n",
    "        p = 0\n",
    "        q = l-1\n",
    "        while p <= q:\n",
    "            su = SQRS[p] + SQRS[q]\n",
    "            if su == c:\n",
    "                res = True\n",
    "                break\n",
    "            elif su < c:\n",
    "                p += 1\n",
    "            elif su > c:\n",
    "                q -= 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        max_num = int(c ** 0.5)\n",
    "        list_nums = list(range(max_num+1))\n",
    "        ptr_begin, ptr_last = 0, len(list_nums)-1\n",
    "        while ptr_begin != ptr_last:\n",
    "            a, b = list_nums[ptr_begin], list_nums[ptr_last]\n",
    "            if c == (a ** 2 + b ** 2):\n",
    "                return True\n",
    "            if c < (a ** 2 + b ** 2):\n",
    "                ptr_last -= 1\n",
    "            else:\n",
    "                ptr_begin += 1\n",
    "        \n",
    "        a, b = list_nums[ptr_begin], list_nums[ptr_last]\n",
    "        if c == (a ** 2 + b ** 2):\n",
    "            return True\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        s=list(range(0,int(math.sqrt(c))+1))\n",
    "        l,r=0,len(s)-1\n",
    "            \n",
    "        while l<=r:\n",
    "            sum_s=s[l]*s[l]+s[r]*s[r]\n",
    "            if sum_s==c:\n",
    "                return True\n",
    "            elif sum_s>c:\n",
    "                r-=1\n",
    "            else:\n",
    "                l+=1\n",
    "        return False\n",
    "#print(Solution().judgeSquareSum(4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        import math\n",
    "        end = int(math.sqrt(c)) + 1\n",
    "        numbers = list(map(lambda x: x * x, range(end)))\n",
    "        left, right = 0, len(numbers) - 1\n",
    "        while left <= right:\n",
    "            sum_ = numbers[left] + numbers[right]\n",
    "            if sum_ < c:\n",
    "                left += 1\n",
    "            elif sum_ > c:\n",
    "                right -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        max_value = int(math.sqrt(c))\n",
    "        nums = [num ** 2 for num in range(max_value + 1)]\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[left] == c:\n",
    "                return True\n",
    "\n",
    "            if nums[right] + nums[right] == c:\n",
    "                return True\n",
    "\n",
    "            num_sum = nums[left] + nums[right]\n",
    "            if num_sum == c:\n",
    "                return True\n",
    "\n",
    "            if num_sum < c:\n",
    "                left += 1\n",
    "\n",
    "            if num_sum > c:\n",
    "                right -= 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "\n",
    "        sq = int(math.sqrt(c))\n",
    "        list1 = list(range(sq+1))\n",
    "        left = 0\n",
    "        right = sq\n",
    "\n",
    "        while left <= right:\n",
    "            x1 = list1[left]**2 \n",
    "            x2 = list1[right]**2\n",
    "            if x1 + x2 == c:\n",
    "                return True\n",
    "            elif x1 + x2 > c:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        sw=0\n",
    "        a=[]\n",
    "        for i in range(int(pow(c,0.5))+1):\n",
    "            a.append(i)\n",
    "        left =0\n",
    "        right=len(a)-1\n",
    "        while left<=right:\n",
    "            if c<a[left]*a[left]+a[right]*a[right]:\n",
    "                right-=1\n",
    "            elif c>a[left]*a[left]+a[right]*a[right]:\n",
    "                left+=1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        l = [i for i in range(int(sqrt(c))+1)]\n",
    "        i, j = 0, 0\n",
    "        for i in l:\n",
    "            k = sqrt(c - i * i)\n",
    "            if int(k) == k:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        li = [i for i in range(int(c ** 0.5) + 1)]\n",
    "        i, j = 0, len(li) - 1\n",
    "        while i <= j:\n",
    "            if i * i + j * j == c:\n",
    "                return True\n",
    "            elif i * i + j * j < c:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "\n",
    "        num_lst = list(range(int(c**(1/2))+1))\n",
    "\n",
    "        left_p = 0\n",
    "        right_p = len(num_lst) - 1\n",
    "\n",
    "        for ii in range(len(num_lst)):\n",
    "\n",
    "            if (num_lst[left_p]**2 + num_lst[right_p]**2) > c:\n",
    "                right_p -= 1\n",
    "            elif (num_lst[left_p]**2 + num_lst[right_p]**2) < c:\n",
    "                left_p += 1\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        left = 0\n",
    "        nums = list(range(int(c ** 0.5) + 1))\n",
    "        right = len(nums) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            if nums[left] ** 2 + nums[right] ** 2 == c:\n",
    "                return True\n",
    "            elif nums[left] ** 2 + nums[right] ** 2 > c:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        li = list(range(int(c**0.5+1)))\n",
    "        l, r = 0, len(li)-1\n",
    "        while l <= r:\n",
    "            if li[l]**2 + li[r]**2 == c:\n",
    "                return True\n",
    "            elif li[l]**2 + li[r]**2 > c:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        index1 = 0\n",
    "        index2 = int((c + 1)**0.5)\n",
    "        nums = list(range(index2 + 1))\n",
    "        while index1 <= c ** 0.5:\n",
    "            if nums[index1] **2 + nums[index2] ** 2 == c:\n",
    "                return True\n",
    "            elif nums[index1] **2 + nums[index2] ** 2 < c:\n",
    "                index1 += 1\n",
    "                if index1 > index2:\n",
    "                    break\n",
    "            else:\n",
    "                index2 -= 1\n",
    "                if index1 > index2:\n",
    "                    break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 0:\n",
    "            return True\n",
    "        \n",
    "        candidate_list = [i for i in range(0, int(math.sqrt(c)) + 1)]\n",
    "        left = 0\n",
    "        right = len(candidate_list) - 1\n",
    "        while (left != right):\n",
    "            if candidate_list[left]**2 + candidate_list[right]**2 == c or candidate_list[left]**2 * 2 == c or candidate_list[right]**2 * 2 == c:\n",
    "                return True\n",
    "            elif candidate_list[left]**2 + candidate_list[right]**2 < c:\n",
    "                left += 1\n",
    "            elif candidate_list[left]**2 + candidate_list[right]**2 > c:\n",
    "                right -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        a, b = 0, int(sqrt(c))+1\n",
    "        records = [-1 for i in range(b+1)]\n",
    "        while a <= b:\n",
    "            if records[a] >= 0:\n",
    "                a2 = records[a]\n",
    "            else:\n",
    "                a2 = a * a\n",
    "                records[a] = a2\n",
    "            if records[b] >= 0:\n",
    "                b2 = records[b]\n",
    "            else:\n",
    "                b2 = b * b\n",
    "                records[b] = b2\n",
    "            sum = a2 + b2\n",
    "            if sum == c:\n",
    "                return True\n",
    "            elif sum < c:\n",
    "                a += 1\n",
    "            else:\n",
    "                b -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        m = []\n",
    "        i = 0\n",
    "        while i**2<=c:\n",
    "            m.append(i**2)\n",
    "            i += 1\n",
    "        i,j = 0,len(m)-1\n",
    "        while i<=j:\n",
    "            if m[i]+m[j]<c:\n",
    "                i += 1\n",
    "            elif m[i]+m[j]>c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        squares = [i*i for i in range(46341)]\n",
    "        i, j = 0, len(squares) - 1\n",
    "        while i <= j:\n",
    "            cur = squares[i] + squares[j]\n",
    "            if cur == c:\n",
    "                return True\n",
    "            elif cur < c:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        n = int(math.sqrt(c))\n",
    "        nums = [i ** 2 for i in range(n+2)]\n",
    "        res = False\n",
    "        for i in range(len(nums)):\n",
    "            idx = bisect.bisect_left(nums, c-nums[i])\n",
    "            if nums[i] + nums[idx] == c or nums[i] + nums[idx-1] == c:\n",
    "                res = True\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 0:\n",
    "            return True\n",
    "        nums = [0]\n",
    "        for i in range(1,c+1):\n",
    "            if i**2==c:\n",
    "                return True\n",
    "            if i**2>c:\n",
    "                break\n",
    "            nums.append(i)\n",
    "        left,right=0,len(nums)-1\n",
    "        while left<=right:\n",
    "            if nums[left]**2+nums[right]**2==c:\n",
    "                return True\n",
    "            if nums[left]**2+nums[right]**2>c:\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        import math\n",
    "        n = math.ceil(math.sqrt(c))\n",
    "        if n**2 == c:\n",
    "            return True\n",
    "        l = [i for i in range(n)]\n",
    "        start = 0\n",
    "        end = n - 1\n",
    "        while start <= end:\n",
    "            if l[start]**2 + l[end] ** 2 == c:\n",
    "                return True\n",
    "            elif l[start]**2 + l[end] ** 2 > c:\n",
    "                end -= 1\n",
    "            elif l[start]**2 + l[end] ** 2 < c:\n",
    "                start += 1\n",
    "        return False       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        mmax = floor(sqrt(c))\n",
    "        a = [_ ** 2 for _ in range(mmax + 1)]\n",
    "        left, right = 0, mmax\n",
    "        while left >= 0 and left <= mmax and right >= 0 and right <= mmax:\n",
    "            if a[left] + a[right] > c:\n",
    "                right -= 1\n",
    "            elif a[left] + a[right] < c:\n",
    "                left += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        lst = [x**2 for x in range(0, int(math.sqrt(c)) + 1)]\n",
    "        left, right = 0, len(lst) - 1\n",
    "        while (left <= right):\n",
    "            if (lst[left] + lst[right]) == c:\n",
    "                return True\n",
    "            elif (lst[left] + lst[right]) < c:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 0:\n",
    "            return True\n",
    "        nums = [0]\n",
    "        for i in range(1,c+1):\n",
    "            if i**2==c:\n",
    "                return True\n",
    "            if i**2>c:\n",
    "                break\n",
    "            nums.append(i)\n",
    "        left,right=0,len(nums)-1\n",
    "        while left<=right:\n",
    "            if nums[left]**2+nums[right]**2==c:\n",
    "                return True\n",
    "            if nums[left]**2+nums[right]**2>c:\n",
    "                right-=1\n",
    "            else:\n",
    "                left+=1\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        temp = []\n",
    "        k = int(math.sqrt(c))\n",
    "        for i in range(k+1):\n",
    "            temp.append(i**2)\n",
    "        left,right = 0,len(temp)-1\n",
    "        while left <= right:\n",
    "            if temp[left]+temp[right] > c:\n",
    "                right -= 1\n",
    "            elif temp[left]+temp[right] < c:\n",
    "                left += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def judgeSquareSum(self, c: int) -> bool:\r\n",
    "        MaxNum = c ** 0.5 + 1\r\n",
    "        dp = []\r\n",
    "\r\n",
    "        Num = 0\r\n",
    "        while Num < MaxNum: \r\n",
    "            dp.append(Num * Num)\r\n",
    "            Num += 1\r\n",
    "\r\n",
    "        Bidx = 0\r\n",
    "        Eidx = len(dp) - 1\r\n",
    "        while Eidx >= Bidx: \r\n",
    "            if dp[Bidx] + dp[Eidx] == c: \r\n",
    "                return True\r\n",
    "            elif dp[Bidx] + dp[Eidx] < c: \r\n",
    "                Bidx += 1\r\n",
    "            else :\r\n",
    "                Eidx -= 1\r\n",
    "        return False\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        def binarySearch(arr,target):\n",
    "            if len(arr)==0:\n",
    "                return -1\n",
    "            left,right=0,len(arr)\n",
    "            while left<right:\n",
    "                mid=(left+right)//2\n",
    "                if arr[mid]==target:\n",
    "                    return mid\n",
    "                elif arr[mid]<target:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid\n",
    "            if left!=len(arr) and arr[left]==target:\n",
    "                return left\n",
    "            return -1\n",
    "        n=0\n",
    "        while n**2<=c:\n",
    "              n+=1\n",
    "        nums=[i**2 for i in range(n)]\n",
    "        for num in nums:\n",
    "            x = binarySearch(nums, c-num)\n",
    "            if x != -1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        lst=[]\n",
    "        for i in range(0,pow(2,16)):\n",
    "            lst.append(i*i)\n",
    "        for i in lst:\n",
    "            if i <=c:\n",
    "                x=bisect_left(lst,c-i)\n",
    "                if x!=len(lst) and c-i==lst[x]:\n",
    "                    return True\n",
    "                # if c-i in lst:\n",
    "                    # print(i,c-i)\n",
    "                    # return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理法，枚举整数范围内所有有整数平方根的数\n",
    "lis = []\n",
    "for i in range(46340):\n",
    "    lis.append(i ** 2)\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # 到这里就类似于力扣第一题两数之和了\n",
    "        s = set()\n",
    "        for i in lis:\n",
    "            if i > c: break\n",
    "            if c - i in s: return True\n",
    "            s.add(i)\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        # 解法2: 双指针\n",
    "        l, r = 0, int(sqrt(c))\n",
    "        while l <= r:\n",
    "            # 这里算平方使用l ** 2 是个性能陷阱，导致整体用时多一倍\n",
    "            v = l * l + r * r\n",
    "            if v == c: return True\n",
    "            if v < c: l += 1\n",
    "            else: r -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        sq = []\n",
    "        for i in range(c+1):\n",
    "            ss = i**2\n",
    "            if ss <= c:\n",
    "                sq.append(ss)\n",
    "            else:\n",
    "                break\n",
    "        low = 0\n",
    "        high = len(sq) - 1\n",
    "        while low <= high:\n",
    "            if sq[low] + sq[high] == c:\n",
    "                return True\n",
    "            elif sq[low] + sq[high] > c:\n",
    "                high -= 1\n",
    "            else:\n",
    "                low += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        arr = set()\n",
    "        tmp = 0\n",
    "        while tmp**2 <= c:\n",
    "            arr.add(tmp*tmp)\n",
    "            tmp += 1\n",
    "\n",
    "        for key in arr:\n",
    "            if c-key in arr: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    \n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c==0:\n",
    "            return True\n",
    "        i = 1\n",
    "        sortedSet = SortedList([0])\n",
    "        while (i-1)*(i-1) <= c:\n",
    "            index = sortedSet.bisect_left(c-(i*i))\n",
    "            if index != len(sortedSet) and sortedSet[index]+(i*i)==c:\n",
    "                return True\n",
    "            if 2*(i*i)==c:\n",
    "                return True\n",
    "            sortedSet.add(i*i)\n",
    "            i+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        tmp = []\n",
    "        for i in range(65536):\n",
    "            tmp.append(i*i)\n",
    "        \n",
    "        def binary(c,l,r,x):\n",
    "            if l < r:\n",
    "                mid = int((l+r)/2)\n",
    "                if c[mid] == x:\n",
    "                    return mid\n",
    "                elif c[mid] > x:\n",
    "                    r = mid\n",
    "                    return binary(c,l,r,x)\n",
    "                elif c[mid] < x:\n",
    "                    l = mid+1\n",
    "                    return binary(c,l,r,x)\n",
    "            return -1\n",
    "        \n",
    "        l = len(tmp)\n",
    "        for num in tmp:\n",
    "            if c - num < 0:\n",
    "                break\n",
    "            if binary(tmp,0,l,c-num) != -1:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        sq=set()\n",
    "        for i in range(floor(math.sqrt(c))+1):\n",
    "            sq.add(i**2)\n",
    "        for j in sq:\n",
    "            if c-j in sq:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        base = [i**2 for i in range(2**16+1)]\n",
    "        r = bisect.bisect_left(base, c)\n",
    "        if base[r] == c:\n",
    "            return True\n",
    "        r -= 1\n",
    "        l = 0\n",
    "        while l <= r:\n",
    "            t = base[l] + base[r]\n",
    "            if t == c:\n",
    "                return True\n",
    "            if t > c:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        a = int(c**0.5)\n",
    "        voc = set()\n",
    "        for i in range(0, a+1):\n",
    "            voc.add(i**2)\n",
    "            if c - i**2 in voc:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        left=0\n",
    "        right=int(math.sqrt(c))\n",
    "        num_list = []\n",
    "        for i in range(right+1):\n",
    "            num_list.append(i)\n",
    "        if c==3:\n",
    "            return False\n",
    "        print(num_list)\n",
    "        print('left:',left,'right:',right)\n",
    "        while left<=right:\n",
    "            if num_list[left]*num_list[left]+num_list[right]*num_list[right]==c:\n",
    "               \n",
    "                return True\n",
    "            elif num_list[left]*num_list[left]+num_list[right]*num_list[right]>c:\n",
    "                \n",
    "                right = right-1\n",
    "            else:\n",
    "                left = left+1\n",
    "        if num_list[left]*num_list[left]+num_list[right]*num_list[right]!=c:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def judgeSquareSum(self, c: int) -> bool:\r\n",
    "        s = set()\r\n",
    "        for i in range(0, int(c ** 0.5)  + 1):\r\n",
    "            s.add(i*i)\r\n",
    "\r\n",
    "        for e in s:\r\n",
    "            if c-e in s:\r\n",
    "                return True\r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: list, target: int) -> list:\n",
    "        result = []\n",
    "\n",
    "        idx_1 = 0\n",
    "        idx_2 = len(numbers) - 1\n",
    "\n",
    "        if target < numbers[idx_1]:\n",
    "            return result\n",
    "\n",
    "        while idx_1 <= idx_2:\n",
    "            if numbers[idx_1] + numbers[idx_2] > target:\n",
    "                idx_2 -= 1\n",
    "            elif numbers[idx_1] + numbers[idx_2] < target:\n",
    "                idx_1 += 1\n",
    "            else:\n",
    "                result = [idx_1 + 1, idx_2 + 1]\n",
    "                break\n",
    "        return result\n",
    "\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c < 0:\n",
    "            return False\n",
    "\n",
    "        numbers = [n**2 for n in range(2**16)]\n",
    "        if self.twoSum(numbers, c):\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        n = int(math.sqrt(c)) + 1\n",
    "        hashmap = set(i**2 for i in range(n+1))\n",
    "\n",
    "        for item in hashmap:\n",
    "            if (c-item) in hashmap:\n",
    "                return True\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        integer = ceil(c**0.5)\n",
    "        num = [i for i in range(integer+1)]\n",
    "        print(num)\n",
    "        i = 0\n",
    "        j = len(num)-1\n",
    "        result = False\n",
    "        while i <= j:\n",
    "            sqrt_sum = num[i]**2 + num[j]**2\n",
    "            if sqrt_sum > c:\n",
    "                j -= 1\n",
    "            elif sqrt_sum < c:\n",
    "                i += 1\n",
    "            else:\n",
    "                result = True\n",
    "                break\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "\n",
    "        mylist = []\n",
    "        for i in range(c+1):\n",
    "            if i ** 2 <= c:\n",
    "                mylist.append(i**2)\n",
    "            else:\n",
    "                break\n",
    "        i, j = 0, len(mylist)-1\n",
    "        \n",
    "        while i <= j:\n",
    "            if mylist[i] + mylist[j] == c:\n",
    "                return True\n",
    "            elif mylist[i] + mylist[j] > c:\n",
    "                j -= 1\n",
    "            elif mylist[i] + mylist[j] < c:\n",
    "                i += 1\n",
    "        print(mylist)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        nums = list(range(0,int(math.sqrt(c)+1)))\n",
    "        print(nums)\n",
    "        i,j = 0,len(nums)-1\n",
    "        val = nums[i]**2 + nums[j]**2\n",
    "        print('val',val)\n",
    "        while i<=j:\n",
    "            if nums[i]**2 + nums[j]**2 == c:\n",
    "                return True\n",
    "            elif nums[i]**2 + nums[j]**2 >c:\n",
    "                j-=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return False\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        nums_list = list(range(int(pow(c, 0.5)) + 1))\n",
    "        left, right = 0, len(nums_list) - 1\n",
    "        while left <= right:\n",
    "            a = pow(nums_list[left], 2)\n",
    "            b = pow(nums_list[right], 2)\n",
    "            if a + b == c:\n",
    "                return True\n",
    "            if a + b < c:\n",
    "                left += 1\n",
    "            if a + b > c:\n",
    "                right -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        #c本身可以被开平方的直接True\n",
    "        #c-1可以被开平方的也True\n",
    "        #c-4,c-9,c-16\n",
    "        # if c<3:\n",
    "        #     return True\n",
    "\n",
    "        arr=[x for x in range(int(c**0.5+1))]\n",
    "        print(arr)\n",
    "        lzz,rzz=0,len(arr)-1\n",
    "\n",
    "        while lzz<=rzz:\n",
    "            if arr[lzz]**2+arr[rzz]**2==c:\n",
    "                return True\n",
    "            elif arr[lzz]**2+arr[rzz]**2>c:\n",
    "                rzz-=1\n",
    "            else:\n",
    "                lzz+=1\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        #c本身可以被开平方的直接True\n",
    "        #c-1可以被开平方的也True\n",
    "        #c-4,c-9,c-16\n",
    "        if c<3:\n",
    "            return True\n",
    "\n",
    "        arr=[x for x in range(int(c**0.5+1))]\n",
    "        print(arr)\n",
    "        lzz,rzz=0,len(arr)-1\n",
    "\n",
    "        while lzz<=rzz:\n",
    "            if arr[lzz]**2+arr[rzz]**2==c:\n",
    "                return True\n",
    "            elif arr[lzz]**2+arr[rzz]**2>c:\n",
    "                rzz-=1\n",
    "            else:\n",
    "                lzz+=1\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        max_factor = int(math.sqrt(c))\n",
    "        square_list = [r*r for r in range(max_factor+1)]\n",
    "        print(square_list)\n",
    "        i = 0\n",
    "        j = max_factor\n",
    "        while True:\n",
    "            print(square_list[i])\n",
    "            print(square_list[j])\n",
    "            if square_list[i] + square_list[j] == c:\n",
    "                return True\n",
    "            elif square_list[i] + square_list[j] > c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "            if i > j:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        max_factor = 0\n",
    "        for i in range(c+1):\n",
    "            if i * i >= c:\n",
    "                max_factor = i\n",
    "                break\n",
    "        square_list = [r*r for r in range(max_factor+1)]\n",
    "        print(square_list)\n",
    "        i = 0\n",
    "        j = max_factor\n",
    "        while True:\n",
    "            print(square_list[i])\n",
    "            print(square_list[j])\n",
    "            if square_list[i] + square_list[j] == c:\n",
    "                return True\n",
    "            elif square_list[i] + square_list[j] > c:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "            if i > j:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # c不一定是一个平方数\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "\n",
    "        squared = []\n",
    "        for i in range(int(math.sqrt(c)) + 1):\n",
    "            squared.append(i * i)\n",
    "        \n",
    "        squared_set = set(squared)\n",
    "        \n",
    "        for n in squared:\n",
    "            if c - n >= 0:\n",
    "                if c - n in squared_set:\n",
    "                    return True \n",
    "            else:\n",
    "                break \n",
    "            \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        s = set([i**2 for i in range(46342)])\n",
    "        for i in s: \n",
    "            if c-i in s: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c <= 4:\n",
    "            if c != 3:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            square_nums = []\n",
    "            max_num = int(math.sqrt(c)) + 1\n",
    "            for i in range(max_num):\n",
    "                square_nums.append(i**2)\n",
    "            square_nums_set = set(square_nums)\n",
    "            res = False\n",
    "            for i in range(len(square_nums)):\n",
    "                if c-square_nums[i] in square_nums_set:\n",
    "                    res = True\n",
    "                    break\n",
    "                else:\n",
    "                    pass\n",
    "            return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        a = [math.pow(i,2) for i in range(int(math.sqrt(c)+1))]\n",
    "        # print(a)\n",
    "        a = set(a)\n",
    "        for i in a:\n",
    "            if c-i in a:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        square_nums = []\n",
    "        num = 0 # 题目只需要是两个整数 可以为0 \n",
    "        while num ** 2 <= c:\n",
    "            square_nums.append(num ** 2) # 天然有序的平方数列表\n",
    "            num += 1\n",
    "        \n",
    "        s = 0\n",
    "        e = len(square_nums) - 1\n",
    "\n",
    "        while s <= e:\n",
    "            if square_nums[s] + square_nums[e] < c:\n",
    "                s += 1\n",
    "            elif square_nums[s] + square_nums[e] > c:\n",
    "                e -= 1\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgeSquareSum(self, c: int) -> bool:\n",
    "        if c == 0:\n",
    "            return True\n",
    "    \n",
    "        mid = int(sqrt(c))\n",
    "        candidate = [i for i in range(0, mid+1)]\n",
    "        p1 = 0\n",
    "        p2 = len(candidate) - 1\n",
    "        while(p1 <= p2):\n",
    "            if candidate[p1] * candidate[p1] + candidate[p2] * candidate[p2] < c:\n",
    "                p1 = p1 + 1\n",
    "            elif candidate[p1] * candidate[p1] + candidate[p2] * candidate[p2] > c:\n",
    "                p2 = p2 - 1\n",
    "            elif candidate[p1] * candidate[p1] + candidate[p2] * candidate[p2] == c:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
